1. Field of the Invention
The present invention relates to the field of electronic design automation (EDA). More specifically, the present invention relates to wire routing within the field of electronic design automation used in the design and fabrication of integrated circuit devices.
2. Related Art
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist and automate most steps of the circuit design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or xe2x80x9ccells.xe2x80x9d Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually. To automate the circuit design and fabrication of integrated circuit devices, electronic design automation (EDA) systems have been developed.
An EDA system is a computer software system designers use for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.) and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated by the EDA system into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation.
A netlist describes the IC design and is composed of nodes (elements) and edges, e.g., connections between nodes, and can be represented using a directed cyclic graph structure having nodes which are connected to each other with signal lines. The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device.
More specifically, within a typical EDA system, the circuit designer first produces a high-level description of the circuit in a hardware description language such as Verilog or VHDL. This high-level description is converted into a netlist using a computer implemented synthesis process such as a the xe2x80x9cDesign Compilerxe2x80x9d by Synopsys of Mountain View, Calif. A netlist is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (xe2x80x9cnetsxe2x80x9d). Importantly, the netlist does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of a computer controlled placement process and a computer controlled routing process.
The placement process finds a location for each cell on a circuit board or silicon chip. The locations are specified, typically, in two dimensional spatial coordinates, e.g., (x, y) coordinates, on the circuit board or silicon chip. The locations are typically selected to optimize certain objectives such as wire length, wire routablility, circuit speed, circuit power consumption, and/or other criteria, subject to the condition that the cells are spread evenly over the circuit board or silicon chip and that the cells do not overlap with each other. The output of the automatic computer controlled cell placement process includes a data structure including the (x, y) location for each cell of the IC design.
Next, the designer supplies the netlist and the cell location data structure, generated by the placement program, to a computer implemented automatic wire routing process (xe2x80x9crouterxe2x80x9d). The router generates wire geometry within data structure for connecting pins together. The wire geometry data structure and cell placement data structure together are used to make the final geometric database needed for fabrication of the circuit. Routers typically include a course routing process and a fine routing process. The coarse router provides a general path for the routing that is done at the detail stage. The coarse router examines at the level of the whole integrated circuit chip and its available resources and determines what the rough pathways should be from a topological standpoint. The fine or detail router lays down the actual geometries and connected wire segments in the appropriate layers as a wire connection may span multiple layers. The fine router creates wire routes that are xe2x80x9cclean,xe2x80x9d e.g., do not have design rule violations, do not overlap other structures and can be fabricated.
FIG. 1 illustrates a layout configuration 10 used in a typical grid-based router. Within a grid-based router, wires are routed along defined and equally spaced grid lines of a grid array. Horizontal 30 and vertical 32 grid lines are shown for an exemplary grid array of layout 10. To route wires between a source pin and a target (e.g., destination) pin, the grid lines must be used in a grid-based router. For instance, wire route 18 that couples pins on block 12 and 14 utilizes, and is aligned with, the horizontal and vertical grid lines. Grid lines of the grid array are used in the routing process to speed up the process of finding the wire routing solutions by reducing the number of pathways to consider for routing. However, the grid-based router approach also has several disadvantages which are described below.
One disadvantage of grid-based routers is that they have trouble routing with circuit blocks that do not use a single defined grid array, as is common in today""s complex circuit implementations. Modern integrated circuit designs (e.g., xe2x80x9csystem-on-a-chipxe2x80x9d designs) typically include several custom integrated circuit designs that are implemented by different companies. Therefore, these custom designs may or may not use the same grid array dimensions as used by the layout 10 of FIG. 1. Further, hand-designed integrated circuits, like circuit 16, may not even use any grid array at all. For instance, pins 4 and pins 6 of the custom designs 12 and 14, respectively, do not align with the grid array of grid lines 30 and 32 because these circuit blocks use a different dimension grid array. This causes a problem for the grid-based router because pins 6 and 4 do not match the grid array of layout 10 and special time consuming attention needs to be paid to these pins. In some cases, the grid-based router does not have any mechanism for dealing with pins that do not align with the main grid array.
Another disadvantage of grid-based routing is that the routing problem is not really a grid-based problem to begin with. In a grid-based router, the grid array is used to locate minimum cost wire routes. However, wire routing really depends on wire length, wire width and wire separation, not a predefined wire grid array. Wire length and wire geometry dictate signal delay which is an ever increasingly large consideration in modern sub-micron designs. To reduce delay, the wires can be made wider and can be separated a greater distance from each other. Therefore, forcing wires to lie on predefined grid lines does not really address the greater underlying problem of signal delay.
Another disadvantage of grid-based routing is that it tends to waste a large percentage of routable area within an integrated circuit substrate. For instance, consider wire route 20 between block 14 and block 16. This route 20, as shown, is located between grid lines 32b and 32a. If this route 20 were made in the grid array it would consume (e.g., occupy) both of the adjacent grid lines 32b and 32a, even though there is room to run other wires between these grids lines and wire route 20. In a grid-based router, when adjacent grid lines are occupied, it is not possible to route a wire there though even though there might be room for such.
Accordingly, what is needed is a routing process that does not have the disadvantageous associated with the grid-based routing process described above. What is needed further is a routing process that is efficient and does not require a relatively long time to complete. What is further needed is a routing process that produces design rule clean wire routes. The present invention provides these advantageous. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.
The present invention pertains to an efficient, gridless, cost-based coarse router having layer assignment for a computer controlled integrated circuit design. The coarse routing process is used during the wire routing phase of an integrated circuit design and fabrication process. During the coarse wire routing process, a number of obstructions are defined. Next, the horizontal and vertical passages between adjacent obstructions, through which wires may be routed, are determined. The costs for possible wire paths connecting a pair of pins are computed based upon wire density histograms associated with the various passages through which the paths traverse. The most cost effective path is then selected. In order to increase the processing speed, the present invention performs several pruning and optimization heuristics that are directed to provide a good clean wire route without necessarily wasting effort locating the lowest cost solution. In some instances, there may be areas which are overly congested. For overly congested areas, a pseudo obstruction is artificially created by the coarse router. Thereby, it may be more cost effective to route a portion of the wire through multiple different metal layers. The histogram is then updated and the next wire is iteratively routed.